perm filename LISP.CDR[F77,JMC] blob
sn#333087 filedate 1978-02-04 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 Comments by Carl Hewitt on an earlier version and their fate in this version.
C00009 00003 ∂06-Dec-77 1111 FTP:CARL at MIT-AI (Carl Hewitt)
C00018 00004 ∂31-Dec-77 1856 FTP:CARL at MIT-AI (Carl Hewitt) My evaluators
C00030 ENDMK
C⊗;
Comments by Carl Hewitt on an earlier version and their fate in this version.
.skip to column 1
***In general I think that the paper is a good start. However, the introductory
paragraph might better serve as a conclusion after to you have introduced and
explained the concepts involved***
[I compromised - making it the second paragraph].
***The following paragraph might be a good place to start the paper***
[This suggestion adopted].
***Perhaps "subexpressions" is better than "subsubexpressions"***fixed
[This suggestion adopted].
***You might want to mention the Advice Taker Project at some point
and explain the relationship of the development of LISP to furthering the
goals of that project***
[done]
***In an appendix it might be worthwhile to present the definition
of EVAL together with the modification that makes upward funargs work.***
Carl: Can you supply me with such an eval?
[I will include the micro-manual as an appendix].
***The following comment about the denotational semantics of RPLACA
and RPLACD seems out of place in the early history of LISP***
[dropped from this place but partially restored further on].
Semantically, they must be represented by functions of state, and only
Michael Gordon really understands them. All this could not be formulated
precisely while LISP was being developed, but it was clear that
%2rplaca%1 and %2rplacd%1 were anomalous.
***Where did FEXPRS come from?***
[answered].
***How did PROG get introduced into LISP?
Was its introduction merely a concession to the FORTRAN mentality.
At this time you already knew how to translate programs that use
gotos into recursive function calls. The resulting functions are tail
recursive so they do not need to use up any storage on the pushdown stack
either interpreted or compiled (see my recent paper in the
A.I. Journal on "Viewing Control Structures as Patterns of Passing
Messages")***
[answered].
***You might also want to mention the pdp-1 LISP system developed by
Peter Deutsch. Was the PDP-1 system the first LISP system to be used
interactively?***
[Don't know.].
***Contemporaneous with the development of the LISP 2 project was the
development of MACLISP on the PDP-6. In fact Alan Kotok explicitly
put the half word instructions into the PDP-6 order code partly as a result
of seeing how useful they would be in the implementation of LISP****
[PDP-6 and its role in LISP discussed].
***Why was the function LABEL was included in LISP?***
[answered].
***Why were RPLACA and RPLACD considered to be more anomalous than
PUTPROP and GETPROP?***
[I don't want to discuss the property list functions].
***The following paragraph makes a good point that could be backed up with
specific examples if the paragraph were placed later in the paper***
[This point not specifically responded to].
***The next paragraph seems a bit disjointed. Many topics have
been superficially mentioned so far. Perhaps a better approach
is to cover the topics in historical order as you do later in the paper***
[I made it the second paragraph].
In addition to its core consisting of recursive conditional
expression and Boolean expression definitions built up from the
three functions %2car%1, %2cdr%1 and %2cons%1 and the predicates
%2atom%1 and %2eq%1, LISP has many features adopted from other
programming languages of the late fifties and early sixties.
A recurrent issue has always been how to handle free variables in function
definitions. This problem has also plagued Algol and other programming
languages, and a compromise has always been necessary between definitional
power and high speed implementation by interpreters and compilers.
[omitted as suggested].
***The compatibility between the LISP compiler and interpreter
has been one of its most important innnovations. This allows
the convenience of interactive editing and debugging afforded by
interpreters while preserving the efficiency that can be obtained
from compiled code. However, the LISP interpreter and compiler
were nor perfectly compatible. You might usefully discuss
SPECIAL and COMMON variables.***
[Tentatively, I have decided not to raise this issue; you might
raise it in commentary if you want].
∂06-Dec-77 1111 FTP:CARL at MIT-AI (Carl Hewitt)
Date: 6 DEC 1977 1410-EST
From: CARL at MIT-AI (Carl Hewitt)
To: jmc at SU-AI
Dear John:
I think that you did a good job on the paper. What it needs now is input
from your colleagues in the development of LISP. What do you think of the idea
of sending a copy to each of them?
I liked your section on the micro-manual for LISP and
thought that it was particularly appropriate.
Below some utility functions are defined which will be used in the LISP
interpreters:
(defun bind←identifiers (identifiers values environment expression)
(cond ((null identifiers)
(cond ((null values)
environment)
(t (error '|Too Few Arguments| expression))))
((null values)
(error '|Too Many Arguments| expression))
(t (cons (list (car identifiers) (car values))
(bind←identifiers (cdr identifiers)
(cdr values)
environment
expression)))))
(defun lookup (identifier environment)
(cond ((null environment)
(error '|Unbound Variable| identifier))
((equal identifier (caar environment))
(cadar environment))
(t (lookup identifier (cdr environment)))))
(defun list←of←values (expressions environment)
(cond ((null expressions)
nil)
(t (cons (eval (car expressions) environment)
(list←of←values (cdr expressions) environment)))))
(defun eval←list (current←value expressions environment)
(cond ((null expressions)
current←value)
(t (eval←list (eval (car expressions) environment)
(cdr expressions)
environment))))
!
First define the evaluator which uses dynamic scoping:
(defun eval (expression environment)
(cond ((atom expression)
(cond ((numberp expression)
expression)
(t (lookup expression environment))))
((eq (car expression) 'quote)
(cadr expression))
((eq (car expression) 'lambda)
expression)
((eq (car expression) 'cond)
(eval←cond←clauses (cdr expression) environment))
(t (apply (eval (car expression) environment)
(list←of←values (cdr expression) environment)
expression
environment))))
(defun apply (procedure arguments expression environment)
(cond ((primitive? procedure)
(apply←primitive procedure arguments))
((eq (car procedure) 'lambda)
(eval←list (eval (caddr procedure)
(bind←identifiers (cadr procedure) environment expression))
(cdddr procedure)
(bind←identifiers (cadr procedure) environment expression)))
(t (error '|Unknown Procedure| (list procedure arguments)))))
(defun eval←cond←clauses (clauses environment)
(cond ((null clauses)
nil)
((eval (caar clauses) environment)
(eval←list 't (cdr clauses) environment))
(t (eval←cond←clauses (cdr clauses) environment))))
!
Now by changing the way that lambda expressions are evaluated
we obtain an interpreter which uses lexical scoping [like the lambda calculus of Church
and ALGOL-60]:
(defun eval (expression environment)
(cond ((atom expression)
(cond ((numberp expression)
expression)
(t (lookup expression environment))))
((eq (car expression) 'quote)
(cadr expression))
((eq (car expression) 'lambda)
(list 'closure (cdr expression) environment))
((eq (car expression) 'cond)
(eval←cond←clauses (cdr expression) environment))
(t (apply (eval (car expression) environment)
(list←of←values (cdr expression) environment)
expression))))
(defun apply (procedure arguments expression)
(cond ((primitive? procedure)
(apply←primitive procedure arguments))
((eq (car procedure) 'closure)
(eval←list (eval (cadadr procedure)
(bind←identifiers (caadr procedure)
arguments
(caddr procedure)
expression))
(cddadr procedure)
(bind←identifiers (caadr procedure)
arguments
(caddr procedure)
expression))
(eval (cadadr procedure)
))
(t (error '|Unknown Procedure| (list procedure arguments)))))
The definition of eval←cond←clauses is the same as above.
!
Note that if the version of eval that uses lexical scoping is adopted then
the procedures cons, car, and cdr need no longer be taken as primitives since
they can easily be defined as follows:
(defun cons (x y)
(lambda (message)
(cond ((equal message 'car)
x)
((equal message 'cdr)
y)
((equal message 'print)
(print '|(|)
(aprint x)
(aprint←sequence y)
(print '|)|))
(t (error '|Unknown Message| message)))))
(defun car (l)
(l 'car))
(defun cdr (l)
(l 'cdr))
(defun aprint (x)
(cond ((atom x)
(print x))
(t (x 'print))))
(defun aprint←sequence (l)
(cond ((null l))
((null (cdr l))
(aprint (car l))
(t
(aprint (car l))
(print '| |)
(aprint←sequence (cdr l)))))
!
ACKNOWLEDGEMENTS
The above interpreters are based on a very elegant one developed
by Jerry Sussman. The term "closure" is due to Peter Landin. The idea of
defining cons as given above is primarily due to Alonzo Church and Alan
Kay.
∂31-Dec-77 1856 FTP:CARL at MIT-AI (Carl Hewitt) My evaluators
Date: 31 DEC 1977 2156-EST
From: CARL at MIT-AI (Carl Hewitt)
Subject: My evaluators
To: jmc at SU-AI
CC: CARL at MIT-AI
My evaluator contains no side effects. It will however interpret
LISP expressions of the form (lambda (x1 ... xk) e1 ... en)
which you may not like and so I have removed this "feature" even though
it is used in all the LISP implementations that I know about.
I apologize for the typo in evaluate←clauses.
Enclosed are two evaluators written in MACLISP that will correctly interpret
definitions written in pure MACLISP subject to the above restriction.
For example (lambda (n) (print n) (print (add1 n))) will not work.
I have tested them on fibonacci, reverse, and create←pair (which is like cons).
The reason that you got the error message that car was not defined is because
of an idiosyncrasy in the treatment of the evaluation of the functional position in
MACLISP. The interpreters given below cater to this idiosyncrasy.
I hope that you find these evaluators more useful than the previous ones.
Sincerely,
Carl
P.S. I am sorry that I did not get back to you sooner with these interpreters
but was tied up with adminstration at the end of the term at M.I.T.
P.P.S. Could you please send me a current copy of the evaluator.
(defun bind←identifiers (identifiers values environment expression)
(cond ((null identifiers)
(cond ((null values)
environment)
(t (error '|Too Few Arguments| expression))))
((null values)
(error '|Too Many Arguments| expression))
(t (cons (list (car identifiers) (car values))
(bind←identifiers (cdr identifiers)
(cdr values)
environment
expression)))))
(defun lookup (identifier environment)
(cond ((null environment)
(error '|Unbound Variable| identifier))
((equal identifier (caar environment))
(cadar environment))
(t (lookup identifier (cdr environment)))))
(defun bound? (identifier environment)
(cond ((null environment)
nil)
((equal identifier (caar environment))
(cadar environment))
(t (bound? identifier (cdr environment)))))
!
; First define the evaluator which uses dynamic scoping:
(defun dynamic←eval (expression environment)
(cond ((atom expression)
(cond ((or (null expression) (equal expression 't) (numberp expression))
expression)
(t (lookup expression environment))))
((atom (car expression))
(cond ((eq (car expression) 'quote)
(cadr expression))
((eq (car expression) 'lambda)
expression)
((eq (car expression) 'cond)
(dynamic←eval←cond←clauses (cdr expression) environment))
(t (dynamic←apply (car expression)
(dynamic←eval←list (cdr expression) environment)
expression
environment))))
(t (dynamic←apply (dynamic←eval (car expression) environment)
(dynamic←eval←list (cdr expression) environment)
expression
environment))))
(defun dynamic←apply (procedure arguments expression environment)
(cond ((atom procedure)
(cond ((get procedure 'expr)
(dynamic←apply (get procedure 'expr) arguments expression environment))
(t
(apply procedure arguments))))
((eq (car procedure) 'lambda)
(dynamic←eval (caddr procedure)
(bind←identifiers
(cadr procedure)
arguments
environment
expression)))
(t (error '|Unknown Procedure| (list procedure arguments)))))
(defun dynamic←eval←cond←clauses (clauses environment)
(cond ((null clauses)
nil)
((dynamic←eval (caar clauses) environment)
(dynamic←eval (cadar clauses) environment))
(t (dynamic←eval←cond←clauses (cdr clauses) environment))))
(defun dynamic←eval←list (expressions environment)
(cond ((null expressions)
nil)
(t (cons (dynamic←eval (car expressions) environment)
(dynamic←eval←list (cdr expressions) environment)))))
!
; Now by changing the way that lambda expressions are evaluated
;we obtain an interpreter which uses lexical scoping [like the lambda calculus of Church
;and ALGOL-60]:
(defun lexical←eval (expression environment)
(cond ((atom expression)
(cond ((or (null expression) (equal expression 't) (numberp expression))
expression)
(t (lookup expression environment))))
((atom (car expression))
(cond ((eq (car expression) 'quote)
(cadr expression))
((eq (car expression) 'lambda)
(list 'closure (cdr expression) environment))
((eq (car expression) 'cond)
(lexical←eval←cond←clauses (cdr expression) environment))
((bound? (car expression) environment)
(lexical←apply (lookup (car expression) environment)
(lexical←eval←list (cdr expression) environment)
expression))
(t (lexical←apply (car expression)
(lexical←eval←list (cdr expression) environment)
expression))))
(t (lexical←apply (lexical←eval (car expression) environment)
(lexical←eval←list (cdr expression) environment)
expression))))
(defun lexical←apply (procedure arguments expression)
(cond ((atom procedure)
(cond ((get procedure 'expr)
(lexical←apply (lexical←eval (get procedure 'expr) ())
arguments
expression))
(t
(apply procedure arguments))))
((eq (car procedure) 'closure)
(lexical←eval (cadadr procedure)
(bind←identifiers (caadr procedure)
arguments
(caddr procedure)
expression)))
(t (error '|Unknown Procedure| (list procedure arguments)))))
(defun lexical←eval←cond←clauses (clauses environment)
(cond ((null clauses)
nil)
((lexical←eval (caar clauses) environment)
(lexical←eval (cadar clauses) environment))
(t (lexical←eval←cond←clauses (cdr clauses) environment))))
(defun lexical←eval←list (expressions environment)
(cond ((null expressions)
nil)
(t (cons (lexical←eval (car expressions) environment)
(lexical←eval←list (cdr expressions) environment)))))
(defun fib (n)
(cond ((zerop n) 1)
((equal n 1) 2)
(t (plus (fib (difference n 1)) (fib (difference n 2))))))
(defun reverse (l)
(cond ((null l)
nil)
(t
(append (reverse (cdr l)) (list (car l))))))
(defun create←pair (x y)
(lambda (m)
(cond ((equal m 'left)
x)
((equal m 'right)
y)
(t (error '|Unknown Message| m)))))
(defun left (l) (l 'left))
(defun right (l) (l 'right))
(lexical←eval '((create←pair 3 4) 'left) ()) ;this wins
(lexical←eval '(left (create←pair 3 4)) ()) ;this wins
(dynamic←eval '((create←pair 3 4) 'left) ()) ;this loses
(dynamic←eval '(left (create←pair 3 4)) ()) ;this loses